package demo3;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSortTest {
    public static void main(String[] args) {
        int[] arr = new int[]{4,2,9,5,1,16,3};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr,int start,int end) {

        if(start >= end) return; // 递归结束条件

        int temp = arr[start];
        int left = start;
        int right = end;

        while(left < right){
            while(left < right && arr[right] > temp){
                right--;
            }
            arr[left] = arr[right];

            while(left < right && arr[left] < temp){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;

        // 递归
        quickSort(arr,start,left);
        quickSort(arr,left+1,end);
    }
}
